package MethodGraph;

import java.util.*;
import java.io.*;

import ptolemy.actor.IOPort;

import util.Util;
import FlowGraph.*;
import FlowGraph.Nodes.*;
import db.ClassData;

//////////////////////////////////////////////////////////////////////////
//// MethodGraph
/**

    Representa o subgrafo gerado a partir de um flow graph, que contem
apenas nos da API do ptolemy.

@author Ivan Jeukens
@version v 0.1 04/06/2002
*/
public class MethodGraph {

    public MethodGraph(FlowGraph fg, ClassData cinfo) {
        _flowGraph = fg;
        _nodes = new LinkedList();
        _edges = new LinkedList();
        _cinfo = cinfo;

        _build();
    }

    ///////////////////////////////////////////////////////////////////
    ////                         public methods                    ////

    public static boolean isIOMethod(String s) {
        if(s.equals("send") || 
           s.equals("get") || 
           s.equals("broadcast") ||
           s.equals("hasRoom") || 
           s.equals("hasToken") ||
           s.equals("isKnown") ||
           s.equals("sendClear") ||
           s.equals("broadcastClear")) return true;

        return false;
    }
    
    public static boolean isIOFGNode(FlowGraphNode n) {
        if(n.getType() == FlowGraphNode.METHOD_CALL && !n.isDeleted()) {
            MethodCallNode mcnode = (MethodCallNode) n;
            if(Util.isSubClass(mcnode.getCallerType(), IOPort.class)) {
                String s = mcnode.getMethodName();
                if(MethodGraph.isIOMethod(s)) {
                    return true;
                }
            }
        }
        return false;
    }

    public MethodGraphEdge connect(MethodGraphNode from, MethodGraphNode to,
            boolean dead) {
        MethodGraphEdge edge = new MethodGraphEdge(from, to, dead);
        from.addOutputEdge(edge);
        to.addInputEdge(edge);
        _edges.add(edge);

        return edge;
    }

    public MethodGraphEdge disconnect(MethodGraphNode from, MethodGraphNode to) {
        MethodGraphEdge edge = from.getOutputEdge(to);
        from.removeOutputEdge(edge);
        to.removeInputEdge(edge);
        _edges.remove(edge);

        return edge;
    }
    
    public String toString() {
        StringBuffer ret = new StringBuffer();
        ret.append("METHOD GRAPH for " + _flowGraph + "\n");
        LinkedList process = new LinkedList();
        process.add(_source);
        HashMap processed = new HashMap();
        while(process.size() > 0) {
            MethodGraphNode mg = (MethodGraphNode) process.remove(0);
            if(processed.containsKey(mg)) continue;

            ret.append(mg.toString() + "\n");

            processed.put(mg, null);
            for(int i = 0;i < mg.outputSize();i++) {
                process.add(mg.getOutputNode(i));
            }
        }
        return ret.toString();
    }

    public boolean containsAPIMethods() {
        if(_nodes.size() == 2) return false;
        return true;
    }

    public void debug(String basepath, int version) {
        try {
            String fname = new String(basepath + "/" + 
                _flowGraph.getMethodName() + "-v" + version + "-MG.dot");
            File dot = new File(fname);
            FileOutputStream fs = new FileOutputStream(dot);
            PrintStream ps = new PrintStream(fs);

            _createDotGraph(ps);

            ps.close();
            fs.close();

            Runtime run = Runtime.getRuntime();
            try {
               Process p = run.exec("dot " + fname + " -o t1");
               p.waitFor();
               p = run.exec("rm " + fname);
               p.waitFor();
               p = run.exec("mv t1 " + fname);
               p.waitFor();
            }
            catch(InterruptedException ex) {
                System.out.println("Exception : " + ex);
            }
        }
        catch(IOException ex) {
            ex.printStackTrace();
        }
    }

    public Iterator nodesIterator() {
        return _nodes.iterator();
    }

    public FlowGraph getFlowGraph() {
        return _flowGraph;
    }

    public LinkedList getTopologicalOrder() {
        if(_topologicalOrder != null) return _topologicalOrder;

        _topologicalOrder = new LinkedList();
        LinkedList process = new LinkedList();
        HashMap processed = new HashMap();
        process.add(_source);
        while(process.size() > 0) {
            MethodGraphNode mgnode = (MethodGraphNode) process.remove(0);
            if(processed.containsKey(mgnode)) continue;

            processed.put(mgnode, null);
            _topologicalOrder.add(mgnode);
            
            for(int i = 0;i < mgnode.outputSize();i++) {
                MethodGraphEdge mgedge = mgnode.getOutputEdge(i);
                if(mgedge.isBack()) continue;
                process.add(mgedge.getTo());
            }
        }

        return _topologicalOrder;
    }

    // So pode fazer isso depois de extrair os dados dos loops....
    public void checkContainsIOMethods() {
        LinkedList top = getTopologicalOrder();
        for(int i = 0;i < top.size();i++) {
            MethodGraphNode mg = (MethodGraphNode) top.get(i);
            mg.checkContainsIOMethods();
        }
    }

    public MethodGraphNode getSource() {
        return _source;
    }

    public MethodGraphNode getSink() {
        return _sink;
    }

    ///////////////////////////////////////////////////////////////////
    ////                        private methods                    ////

    /* Constroi o grafo a partir do flow graph atual. A implementacao ta muito
    porca. Eu calculo mesmo sem precisar. Isso e devido ao deleted */
    private void _build() {
        // System.out.println("Criando mg para " + _flowGraph.getMethodName());
        LinkedList top = _flowGraph.getTopologicalOrder(true);
        LinkedList loopHeads = new LinkedList();
        
        // par um dado FGnode, guarda os nos MG acessiveis e que nao seja SDF
        // dead
        HashMap nodeList = new HashMap();
        // par um dado FGnode, guarda os nos MG acessiveis e que sao SDF dead
        HashMap nodeListDead = new HashMap();

        _source = new MethodGraphNode(null);
        _source.setType(MethodGraphNode.SOURCE);

        _sink = new MethodGraphNode(null);
        _sink.setType(MethodGraphNode.SINK);

        HashMap map = new HashMap();
        map.put(_source, null);

        nodeList.put(_flowGraph.getSource(), map);
        nodeListDead.put(_flowGraph.getSource(), null);

        _nodes.add(_source);
        for(int i = 0;i < top.size();i++) {
            FlowGraphNode n = (FlowGraphNode) top.get(i);
            if(n.getType() == FlowGraphNode.SOURCE) continue;

            // Calcula para o atual no do FG, a lista de nos MG
            HashMap mnew = new HashMap();
            HashMap mnewDead = new HashMap();
            for(int j = 0;j < n.inputSize();j++) {
                FlowGraphNode in = n.getInputNode(j);
                FlowGraphEdge edge = n.getInputEdge(j);
                if(edge.isBack() || edge.isDeleted()) continue;

                HashMap m2 = (HashMap) nodeList.get(in);
                HashMap m2Dead = (HashMap) nodeListDead.get(in);

                if(edge.isSDFDead()) {
                    if(m2 != null) {
                        Iterator ite = (m2.keySet()).iterator();
                        while(ite.hasNext()) {
                            MethodGraphNode mn = (MethodGraphNode) ite.next();
                            mnewDead.put(mn, null);
                        }
                    }
                    if(m2Dead != null) {
                        Iterator ite = (m2Dead.keySet()).iterator();
                        while(ite.hasNext()) {
                            MethodGraphNode mn = (MethodGraphNode) ite.next();
                            mnewDead.put(mn, null);
                        }
                    }
                }
                else {
                    if(m2 != null) {
                        Iterator ite = (m2.keySet()).iterator();
                        while(ite.hasNext()) {
                            MethodGraphNode mn = (MethodGraphNode) ite.next();
                            mnew.put(mn, null);
                        }
                    }
    
                    if(m2Dead != null) {
                        Iterator ite = (m2Dead.keySet()).iterator();
                        while(ite.hasNext()) {
                            MethodGraphNode mn = (MethodGraphNode) ite.next();
                            mnewDead.put(mn, null);
                        }
                    }
                }
            }

            if(isIOFGNode(n)) {
                MethodCallNode mcnode = (MethodCallNode) n;
                MethodGraphNode mgnode = new MethodGraphNode(mcnode);
                _nodes.add(mgnode);

                Iterator ite = (mnew.keySet()).iterator();
                while(ite.hasNext()) {
                    MethodGraphNode mn = (MethodGraphNode) ite.next();
                    connect(mn, mgnode, false);
                }
                ite = (mnewDead.keySet()).iterator();
                while(ite.hasNext()) {
                    MethodGraphNode mn = (MethodGraphNode) ite.next();
                    connect(mn, mgnode, true);
                }
                mnew = new HashMap();
                mnewDead = new HashMap();
                if(n.isSDFMarked()) {
                    mnewDead.put(mgnode, null);
                }
                else {
                    mnew.put(mgnode,  null);
                }
            }
            else
            if(n.getType() == FlowGraphNode.METHOD_CALL && !n.isDeleted()) {
                MethodCallNode mcnode = (MethodCallNode) n;
                if(mcnode.getFlowGraph() != null) {  // cria um link
                    MethodGraphNode mgnode = new MethodGraphNode(mcnode);
                    mgnode.setType(MethodGraphNode.GRAPH_LINK);
                    _nodes.add(mgnode);

                    Iterator ite = (mnew.keySet()).iterator();
                    while(ite.hasNext()) {
                        MethodGraphNode mn = (MethodGraphNode) ite.next();
                        connect(mn, mgnode, false);
                    }
                    ite = (mnewDead.keySet()).iterator();
                    while(ite.hasNext()) {
                        MethodGraphNode mn = (MethodGraphNode) ite.next();
                        connect(mn, mgnode, true);
                    }
                    mnew = new HashMap();
                    mnewDead = new HashMap();
                    if(n.isSDFMarked()) {
                        mnewDead.put(mgnode, null);
                    }
                    else {
                        mnew.put(mgnode,  null);
                    }
                }
            }
            else
            if(n.getType() == FlowGraphNode.SINK) {
                Iterator ite = (mnew.keySet()).iterator();
                while(ite.hasNext()) {
                    MethodGraphNode mn = (MethodGraphNode) ite.next();
                    connect(mn, _sink, false);
                }
                ite = (mnewDead.keySet()).iterator();
                while(ite.hasNext()) {
                    MethodGraphNode mn = (MethodGraphNode) ite.next();
                    connect(mn, _sink, true);
                }
            }
            else
            if((n.getType() == FlowGraphNode.FOR_BEGIN ||
                    n.getType() == FlowGraphNode.DO_BEGIN ||
                    n.getType() == FlowGraphNode.WHILE_BEGIN) && !n.isDeleted()) {
                MethodGraphNode mgnode = new MethodGraphNode(null);
                mgnode.setType(MethodGraphNode.LOOPHEAD);
                // _nodes.add(mgnode);
                mgnode.setLoopHead(n);

                Iterator ite = (mnew.keySet()).iterator();
                while(ite.hasNext()) {
                    MethodGraphNode mn = (MethodGraphNode) ite.next();
                    connect(mn, mgnode, false);
                }
                ite = (mnewDead.keySet()).iterator();
                while(ite.hasNext()) {
                    MethodGraphNode mn = (MethodGraphNode) ite.next();
                    connect(mn, mgnode, true);
                }
                mnew = new HashMap();
                mnewDead = new HashMap();
                if(n.isSDFMarked()) {
                    mnewDead.put(mgnode, null);
                }
                else {
                    mnew.put(mgnode,  null);
                }
                loopHeads.add(mgnode);
            }

            if(n.isSDFMarked()) {
                nodeList.put(n, null);
                mnewDead.putAll(mnew);
                nodeListDead.put(n, mnewDead);
            }
            else {
                nodeList.put(n, mnew);
                nodeListDead.put(n, mnewDead);
            }
        }
        _nodes.add(_sink);

        // Efetua as conexoes entre os nos de API que tem back edge, e o no
        // auxiliar que indica o inicio do loop
        // Processo a lista do fim para o inicio, para processar primeiro
        // loops internos. Assim, quando eu analiso o loop externo, sei se
        // o interno esta vazio ou nao.
        HashMap emptyloop = new HashMap();
        for(int nindex = loopHeads.size() - 1;nindex >= 0;nindex--) {
            MethodGraphNode mg = (MethodGraphNode) loopHeads.get(nindex);
            FlowGraphNode n = (FlowGraphNode) mg.getLoopHead();

            boolean hasback = false;
            // procura os back edges
            for(int i = 0;i < n.inputSize();i++) {
                FlowGraphEdge fgedge = n.getInputEdge(i);
                if(fgedge.isBack()) {
                    FlowGraphNode in = fgedge.getFrom();

                    // para esse no do FG, conecta os nos de API com o inicio
                    // do loop
                    HashMap mnew = (HashMap) nodeList.get(in);
                    HashMap mnewDead = (HashMap) nodeListDead.get(in);

                    // COXA !!! COXA!!! se mnew for null, e que e um no tipo break
                    // ou continue, que ta em um if dead!!!! entao, pula essa aresta.
                    if((in.getType() == FlowGraphNode.CONTINUE ||
                            in.getType() == FlowGraphNode.BREAK) && 
                            mnew == null && mnewDead == null) {
                        continue;
                    }

                    if(mnew != null) {
                        Iterator ite2 = (mnew.keySet()).iterator();
                        while(ite2.hasNext()) {
                            MethodGraphNode m2 = (MethodGraphNode) ite2.next();
                            if((m2 != mg) && (!emptyloop.containsKey(m2))) {
                                MethodGraphEdge edge = connect(m2, mg, false);
                                edge.setIsBack(true);
                                hasback = true;
                            }
                        }
                    }
                    
                    if(mnewDead != null) {
                        Iterator ite2 = (mnewDead.keySet()).iterator();
                        while(ite2.hasNext()) {
                            MethodGraphNode m2 = (MethodGraphNode) ite2.next();
                            if((m2 != mg) && (!emptyloop.containsKey(m2))) {
                                MethodGraphEdge edge = connect(m2, mg, true);
                                edge.setIsBack(true);
                                hasback = true;
                            }
                        }
                    }
                }
            }

            // Elimina um no de inicio de loop desnecessario
            if(!hasback) {
                LinkedList inputs = new LinkedList();
                LinkedList edges = new LinkedList();
                int inputSize = mg.inputSize();
                for(int i = 0;i < inputSize;i++) {
                    MethodGraphNode in = mg.getInputNode(0);
                    MethodGraphEdge edge = disconnect(in, mg);
                    inputs.add(in);
                    edges.add(edge);
                }
                int outputSize = mg.outputSize();
                for(int j = 0;j < outputSize;j++) {
                    MethodGraphNode out = mg.getOutputNode(0);
                    disconnect(mg, out);
                    for(int k = 0;k < inputs.size();k++) {
                        MethodGraphNode in = (MethodGraphNode) inputs.get(k);
                        MethodGraphEdge edge = (MethodGraphEdge) edges.get(k);
                        connect(in, out, edge.isSDFDead());
                    }
                }
                emptyloop.put(mg, null);
            }
            else {
                _nodes.add(mg);
            }
        }

        for(int ncount = 0;ncount < _nodes.size();ncount++) {
            MethodGraphNode mg = (MethodGraphNode) _nodes.get(ncount);
            if(mg.getType() != MethodGraphNode.LOOPHEAD) continue;
            FlowGraphNode n = mg.getLoopHead();

            HashMap processed = new HashMap();
            for(int i = 0;i < mg.inputSize();i++) {
                MethodGraphEdge me = mg.getInputEdge(i);
                if(me.isBack()) {
                    LinkedList process = new LinkedList();
                    process.add(me.getFrom());
                    while(process.size() > 0) {
                        MethodGraphNode in = (MethodGraphNode) process.remove(0);

                        if(processed.containsKey(in)) continue;
                        processed.put(in, null);

                        mg.addLoopBodyNode(in);
                        in.insideLoopBody(mg);

                        for(int k = 0;k < in.inputSize();k++) {
                            MethodGraphEdge edgein = in.getInputEdge(k);
                            // nao processa o corpo do loop interno
                            if(edgein.isBack()) continue;

                            MethodGraphNode in2 = edgein.getFrom();
                            if(in2 == mg) {
                                mg.addFirstLoopNode(in);
                                continue;
                            }
                            process.add(in2);
                        }
                    }
                }
            }

            for(int i = 0;i < mg.outputSize();i++) {
                MethodGraphNode out = mg.getOutputNode(i);
                if(!mg.isFirstLoopNode(out)) {
                    mg.addContinueLoopNode(out);
                }
            }
        }
    }

    private boolean _isEmptyMethodGraph(MethodGraph mg) {
        MethodGraphNode source = mg.getSource();
        if(source.outputSize() == 1) {
            MethodGraphNode out = source.getOutputNode(0);
            if(out.getType() == MethodGraphNode.SINK) return true;
        }
        return false;
    }
    
    private void _createDotGraph(PrintStream ps) {
        StringBuffer buf = new StringBuffer("digraph \" " + _flowGraph.toString() +
          "\" {\n");

        for(int i = 0;i < _nodes.size();i++) {
            MethodGraphNode node = (MethodGraphNode) _nodes.get(i);
            if(node.getType() == MethodGraphNode.SOURCE) {
                buf.append(node.hashCode() + " [shape=box,label=\"SOURCE\"];\n");
            }
            else
            if(node.getType() == MethodGraphNode.SINK) {
                buf.append(node.hashCode() + " [shape=box,label=\"SINK\"];\n");
            }
            else
            if(node.getType() == MethodGraphNode.LOOPHEAD) {
                buf.append(node.hashCode() + 
                    " [shape=box,label=\"LOOP HEAD - " + node.getNTokens() + 
                    "\"];\n");
            }
            else
            if(node.getType() == MethodGraphNode.GRAPH_LINK) {
                buf.append(node.hashCode() + " [shape=box,label=\"GRAPH LINK\"];\n");
            }
            else {
                String s = node.statementString();
                if(s.length() > 30) {
                    s = s.substring(0, 29);
                }
                buf.append(node.hashCode() + " [shape=box,label=\"" + s + 
                " - " + node.getNTokens() + "\"];\n");
            }

            for(int j = 0;j < node.outputSize();j++) {
                MethodGraphEdge edge = node.getOutputEdge(j);
                MethodGraphNode mg = edge.getTo();
                if(edge.isSDFDead()) {
                    buf.append(node.hashCode() + " -> " + mg.hashCode() +
                      " [color=\"green\"];\n");
                }
                else {
                    buf.append(node.hashCode() + " -> " + mg.hashCode() +
                      " [color=\"black\"];\n");
                }
            }
            
        }
        buf.append("}");
        ps.print(buf.toString());
    }

    ///////////////////////////////////////////////////////////////////
    ////                        private variables                  ////

    private ClassData _cinfo;
    private FlowGraph _flowGraph;

    private HashMap _portSources;

    private MethodGraphNode _source;
    private MethodGraphNode _sink;

    private LinkedList _nodes;
    private LinkedList _edges;

    private LinkedList _topologicalOrder;
}
